#!/usr/bin/env python

"""
Sudoku | Sam Auciello | March 2011

A Sudoku solving program using Knuth's dancing links algorithm.

According to Wikipedia:

    Sudoku is a logic-based, combinatorial number-placement puzzle. The objective is
     to fill a 9x9 grid with digits so that each column, each row, and each of the
     nine 3x3 sub-grids that compose the grid (also called "boxes", "blocks",
     "regions", or "sub-squares") contains all of the digits from 1 to 9. The puzzle
     setter provides a partially completed grid, which typically has a unique
     solution.

An example of a sudoku puzzle:

             2     |   4   |   1  
             1 4   |     9 |   7  
                   |   1   | 3    
            -----------------------
               7 3 |     4 |      
             6   5 |       | 9   8
                   | 1     | 7 5  
            -----------------------
                 1 |   2   |      
               2   | 6     |   8 7
               8   |   3   |     6

And its solution:

             2 3 6 | 5 4 7 | 8 1 9
             1 4 8 | 3 6 9 | 5 7 2
             7 5 9 | 8 1 2 | 3 6 4
            -----------------------
             8 7 3 | 9 5 4 | 6 2 1
             6 1 5 | 2 7 3 | 9 4 8
             4 9 2 | 1 8 6 | 7 5 3
            -----------------------
             9 6 1 | 7 2 8 | 4 3 5
             3 2 4 | 6 9 5 | 1 8 7
             5 8 7 | 4 3 1 | 2 9 6

The puzzle can be reduced to an exact cover problem by considdering the rules of
 the puzzle as 4 types of constraints.
 
 1. Each space must have exactly one number
 2. Each row must have exactly one of each number
 3. Each column must have exactly one of each number
 4. Each box must have exactly one of each number
 
Then considder that from a blank grid there are 729 moves we can make.
 (9 possible numbers times 81 possible spaces). Each of these moves satisfies
 one of each of the four types of constraints listed above and eliminates the
 possibility of any of the moves that also satisfies the same constraint.  For
 example, if I choose to put a 3 in the second space of the top row, I eliminate
 the possibility of later putting a 6 in that space since both moves satisfy the
 constraint of there being exactly 1 number in that space.

To turn this problem into the exact cover problem, simply represent constraints
 with columns in a matrix and represent possible moves with rows in a matrix
 containing a 1 in each column for which that move satisfies that constraint and
 a 0 otherwise. Solving the exact cover problem on this matrix will give a
 subset of the rows corrosponding to the moves that can be made to solve the
 puzzle.

Since we are already given some numbers at the start of a sudoku puzzle, it is
 useful to considder them as moves already made. We must start by removing all
 rows in the matrix that conflict with moves already made and for this reason we
 call the reduce sub-routine from the dancing links algorithm on each row that
 corrosponds to a move already made.  Then we call the solve routine and get our
 answer.

Some help came from http://code.google.com/p/narorumo/wiki/SudokuDLX

"""

# Includes #

from dancing_links import Matrix
import random

# Constants #

DEBUG = False
VERBOSE = False
VISUALIZE = False

# Classes #

class Array() :
    """
    A constraint matrix that can be solved by the dancing links algorithm
     representing a sudoku puzzle. Each row in the matrix represents a
     particular number that could be in particular space in the puzzle (not
     taking into account the numbers already filled in). There are thus 9*81 or
     729 rows.
    
    The first 81 columns represent the constraint that a particular space in
     the puzzle must be filled exactly once.  Each row contains 1 in the
     column corrosponding to the space it fills.

    The next 81 columns represent the constraint that a particular row must
     have exactly one of each number.  Each row contains a 1 in the column
     corrosponding to the row its fills with the number it fills it with.
    
    The final 162 columns are the same as the previous 81 except that they
     corrospond to columns and boxes instead of rows.
    
    Rather than actually generate a 729x324 two dimentional list we take
     advantage of the fact that python is duck-typed and instead create an
     object that acts like a two dimentional list and pretends to have 1s in
     the right places.
    """
    def __init__(self) :
        """
        Since the intial matrix contains all possibilities there are no
         variables and thus nothing to initialize. The object exists to fool
         python into thinking its a list of lists
        """
        pass
    def __getitem__(self, index) :
        """
        Returns an object representing a row of the matrix
        """
        number = (index % 9) + 1
        space = index / 9
        col = space % 9
        row = space / 9
        box = (row - (row % 3)) + (col / 3)
        return ArrayRow(number, space, col, row, box)
    def __len__(self) :
        """
        Returns the number of rows
        """
        return 81 * 9

class ArrayRow() :
    """
    A row of the constraint matrix
    """
    def __init__(self, number, space, col, row, box) :
        """
        Initialize the parameters of the row
        """
        self.number = number
        self.space = space
        self.col = col
        self.row = row
        self.box = box
    def __getitem__(self, index) :
        """
        Returns a 1 or 0 depending on whether the row meets the constraint
         corrosponding to the specified column
        """
        if isinstance(index, slice) : # If a slice is asked for generate the
                                        # full list and slice it
            return self.list()[index.start:index.stop:index.step] 
        if 0 <= index <= 80 : # Each space must be filled once
            if index == self.space : return 1
            return 0
        if 81 <= index <= 161 : # Each row must contain each number
            number = ((index - 81) % 9) + 1
            row = ((index - 81) / 9)
            if number == self.number and row == self.row : return 1
            return 0
        if 162 <= index <= 242 : # Each column must contain each number
            number = ((index - 162) % 9) + 1
            col = ((index - 162) / 9)
            if number == self.number and col == self.col : return 1
            return 0
        if 243 <= index <= 323 : # Each box must contain each number
            number = ((index - 243) % 9) + 1
            box = ((index - 243) / 9)
            if number == self.number and box == self.box : return 1
            return 0
    def __len__(self) :
        """
        Returns the number of columns
        """
        return 81 * 4
    def list(self) :
        """
        Returns the row as a list for use in building links
        """
        # This half-way defeats the point but I realized it was necessary too
        #  late and it should work anyway
        return [self[i] for i in range(81 * 4)]

class Puzzle() :
    """
    A sudoku puzzle that can be solved using the Knuth Dancing Links algorithm
    """
    def __init__(self, grid) :
        """
        Initialize the puzzle
        """
        self.grid = grid
    def __repr__(self) :
        """
        A text based representation of the puzzle
        """ # This could stand to be DRYed out a bit but it'll do for now.
        out = ""
        for row in self.grid[0:3] :
            for number in row[0:3] :
                if number == None : out += "  "
                else : out += " " + str(number)
            out+= " |"
            for number in row[3:6] :
                if number == None : out += "  "
                else : out += " " + str(number)
            out+= " |"
            for number in row[6:9] :
                if number == None : out += "  "
                else : out += " " + str(number)
            out += "\n"
        out += "-----------------------\n"
        for row in self.grid[3:6] :
            for number in row[0:3] :
                if number == None : out += "  "
                else : out += " " + str(number)
            out+= " |"
            for number in row[3:6] :
                if number == None : out += "  "
                else : out += " " + str(number)
            out+= " |"
            for number in row[6:9] :
                if number == None : out += "  "
                else : out += " " + str(number)
            out += "\n"
        out += "-----------------------\n"
        for row in self.grid[6:9] :
            for number in row[0:3] :
                if number == None : out += "  "
                else : out += " " + str(number)
            out+= " |"
            for number in row[3:6] :
                if number == None : out += "  "
                else : out += " " + str(number)
            out+= " |"
            for number in row[6:9] :
                if number == None : out += "  "
                else : out += " " + str(number)
            out += "\n"
        return out
    def solve(self, returnCount=False) :
        """
        Generate a constraint matrix, reduce it for each known value in the grid
         and then solve it using the dancing links algorithm
        """
        if VERBOSE : print "\nSUDOKU\n" + str(self)
        matrix = Matrix(Array())
        if VERBOSE : print "Reducing the grid using given numbers..."
        for row in range(9) : # Iterate through spaces in the grid
            for col in range(9) :
                number = self.grid[row][col]
                if number != None : # Reduce using know value
                    matrixCol = 9 * row + col
                    matrixRow = 9 * matrixCol + number - 1
                    matrix[matrixRow, matrixCol].reduce()
        if VERBOSE : print "Running Dancing Links..."
        solutions = matrix.solve() # Run dancing links
        if VERBOSE : print "Returing solution to grid form..."
        if len(solutions) > 0 :
            solution = solutions[0] # Translate solution back onto the grid
            for rowIndex in solution :
                number = (rowIndex % 9) + 1
                space = rowIndex / 9
                col = space % 9
                row = space / 9
                self.grid[row][col] = number
                if VISUALIZE : print self
            if returnCount : return matrix.root.counter
            return self
        return "No solution"

if __name__ == "__main__" :
    a = Puzzle([
        [   9, None, None,    1,    4,    2, None, None,    5],
        [None,    1, None, None, None,    8,    7, None, None],
        [   2, None, None, None,    6, None, None, None,    1],
        [None,    7,    4, None, None,    6, None,    5, None],
        [None,    5, None,    7, None,    1, None,    3, None],
        [None,    6, None,    8, None, None,    2,    1, None],
        [   7, None, None, None,    8, None, None, None,    4],
        [None, None,    3,    6, None, None, None,    2, None],
        [   5, None, None,    4,    1,    9, None, None,    3]
    ])
    print a.solve()
    a = Puzzle([
        [   2, None, None, None,    4, None, None,    1, None],
        [   1,    4, None, None, None,    9, None,    7, None],
        [None, None, None, None,    1, None,    3, None, None],
        [None,    7,    3, None, None,    4, None, None, None],
        [   6, None,    5, None, None, None,    9, None,    8],
        [None, None, None,    1, None, None,    7,    5, None],
        [None, None,    1, None,    2, None, None, None, None],
        [None,    2, None,    6, None, None, None,    8,    7],
        [None,    8, None, None,    3, None, None, None,    6]
    ])
    print a.solve()